package main

import "fmt"

/*
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app");     // 返回 true

说明:
你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。

实现思路：
 - 由于所有输入都是小写字母构成，可以用桶的方式实现，虽然有空间浪费，但是速度最快。
 - 同时要实现搜索词和搜索词前缀。考虑加入布尔标识是否是一个词。但插入词的时候，到词的最后一个字母时，将该节点布尔设为true
 */

type tree struct {
	children [26]*tree
	isWord bool   // 标记是不是一个单词
}

// 构造函数
func Constructor() tree {
	return tree{}
}

// 插入一个单词
func (t *tree)Insert(word string) {
	cur := t
	for i, c := range word {
		n := c - 'a'   // 使用0 - 26 表示a - z
		if cur.children[n] == nil {
			cur.children[n] = &tree{}
		}

		cur = cur.children[n]
		if i == len(word) - 1 {
			cur.isWord = true   // 标记到单词的最后一位
		}
	}
}

// 查询一个单词
func (t *tree)Search(word string) bool {
	cur := t
	for _, c := range word {
		n := c - 'a'
		if cur.children[n] == nil {
			return false
		}
		cur = cur.children[n]
	}
	return cur.isWord
}

// 搜索前缀
func (t *tree)Prefix(prefix string) bool {
	cur := t
	for _, c := range prefix {
		n := c - 'a'
		if cur.children[n] == nil {
			return false
		}
		cur = cur.children[n]
	}
	return true
}


func main() {
	t := Constructor()
	t.Insert("crown")
	t.Insert("wear")
	t.Insert("books")
	fmt.Println(t.Search("wear"))
	fmt.Println(t.Prefix("co"))
}






